package greedyAlgorithm;

//https://leetcode.cn/problems/candy/
public class Candy {
    public int candy(int[] ratings) {
        int index1 = nextMinIndex1(ratings, 0);
        int res = rightCandy(ratings, 0, index1++);
        int lbase = 1;
        int next = 0;
        int rcands = 0;
        int rbase = 0;

        while (index1 != ratings.length) {
            if (ratings[index1] > ratings[index1 + 1]) {
                res += ++lbase;
                index1++;
            } else if (ratings[index1] < ratings[index1 - 1]) {
                next = nextMinIndex1(ratings, index1 - 1);
                rcands = rightCandy(ratings, index1 - 1, next++);
                rbase = next - index1 + 1;
                res += rcands + (rbase > lbase ? -lbase : -rbase);
                lbase = 1;
                index1 = next;
            } else {
                res += 1;
                lbase = 1;
                index1++;
            }
        }
        return res;

    }

    int nextMinIndex1(int[] arr, int start) {
        for (int i = start; i != arr.length - 1; i++) {
            if (arr[i] <= arr[i + 1]) {
                return i;
            }
        }
        return arr.length - 1;
    }


    int rightCandy(int[] arr, int l, int r) {
        int n = r - l + 1;
        return n + n * (n - 1) / 2;
    }
}
